package org.fioma.ui;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;

import org.fioma.general.Read;
import org.fioma.general.ReadStrings;
import org.fioma.general.Tools;
import org.fioma.search.Match;
import org.fioma.search.MatchReadCollection;
import org.fioma.search.MatchReadCollectionFactory;
import org.fioma.tree.InternalNode;
import org.fioma.tree.Node;
import org.fioma.tree.bytes.LabelRefBytesIndex;
import org.fioma.tree.bytes.LabelRefBytesIndexFactory;
import org.fioma.tree.suffixTree.memory.bytes.MemoryBytes;
import org.fioma.tree.suffixTree.memory.ukkonen.SimpleUkkonenMemory;
import org.fioma.tree.suffixTree.memory.ukkonen.SimpleUkkonenSuffixRootMemory;
import org.fioma.tree.suffixTree.memory.ukkonen.SimpleUkkonenSuffixTreeHandlerMemory;
import org.fioma.tree.suffixTree.memory.ukkonen.UkkonenInternalSuffixNodeMemory;
import org.fioma.tree.suffixTree.memory.ukkonen.UkkonenLeafSuffixNodeMemory;
import org.fioma.tree.suffixTree.memory.ukkonen.UkkonenSuffixNodeMemory;
import org.fioma.tree.suffixTree.ukkonen.UkkonenSuffixTree;

public class Fioma {

	// java -Xms400000M -Xmx400000M -verbose:gc -jar fioma.jar 20 320000000000 /projects/Bos_indicus/data/RAW.fastq/August/Caetano_shotguns_700_2_R1.PF.fastq >
	// output.tree.Caetano_shotguns_700_2_R1.PF.fastq
	// echo java -Xms400000M -Xmx400000M -verbose:gc -jar fioma.jar 20 320000000000
	// /projects/Bos_indicus/data/RAW.fastq/August/Caetano_shotguns_700_2_R1.PF.fastq
	// /projects/Bos_indicus/data/RAW.fastq/August/Caetano_shotguns_700_2_R2.PF.fastq
	// /projects/Bos_indicus/data/RAW.fastq/August/Caetano_shotguns_700_1_R1.PF.fastq /projects/Bos_indicus/data/RAW.fastq/Caetano_shotguns_700_1_R2.PF.fastq
	// /projects/Bos_indicus/data/RAW.fastq/Caetano_shotguns_700_3_R1.PF.fastq /projects/Bos_indicus/data/RAW.fastq/Caetano_shotguns_700_3_R2.PF.fastq
	// /projects/Bos_indicus/data/RAW.fastq/Caetano_shotguns_700_4_R1.PF.fastq /projects/Bos_indicus/data/RAW.fastq/Caetano_shotguns_700_4_R2.PF.fastq | qsub
	// -cwd -l mf=400G

	public static int k;
	public static int c; // shiftBack
	public static int e;
	public static int m;
	public static int s;
	public static int j;
	public static int sv;
	public static int ev;
	public static int readsMaxSize;

	public static MatchReadCollectionFactory matchCollectionFactory;

	public static int r1case1 = 0;
	public static int r1case1a = 0;
	public static int r1case2 = 0;
	public static int r1case2a = 0;
	public static int r1case3 = 0;

	public static LabelRefBytesIndexFactory labelFactory;
	public static SimpleUkkonenSuffixTreeHandlerMemory treeHandler;

	/**
	 * @param args
	 * @throws IOException
	 * @throws NumberFormatException
	 */
	public static void main(String[] args) {
		BufferedReader validReads;

		try {
			if (args.length < 8) {
				throw new RuntimeException("Use: Fioma fileReads fileMatePairs k m s e c j sv ev readsMaxSize totalBytes ");
			}
			System.out.println("Max Memory before build the tree " + Runtime.getRuntime().maxMemory());
			System.out.println("Total Memory before build the tree " + Runtime.getRuntime().totalMemory());
			System.out.println("Free Memory before build the tree " + Runtime.getRuntime().freeMemory());
			long timeInic = System.currentTimeMillis();
			String validReadsFileName = args[0];
			String matePairssFileName = args[1];
			k = Integer.parseInt(args[2]);
			m = Integer.parseInt(args[3]); // shiftBack
			s = Integer.parseInt(args[4]);
			e = Integer.parseInt(args[5]);
			c = Integer.parseInt(args[6]);
			j = Integer.parseInt(args[7]);
			sv = Integer.parseInt(args[8]);
			ev = Integer.parseInt(args[9]);
			readsMaxSize = Integer.parseInt(args[10]);
			long totalBytes = Long.parseLong(args[11]);

			System.out.print("Arguments:");
			for (String arg : args) {
				System.out.print(" " + arg);
			}
			System.out.println();

			matchCollectionFactory = new MatchReadCollectionFactory(readsMaxSize, k, c, j);

			if (k <= c) {
				throw new RuntimeException("k must be greater than c.");
			}
			SimpleUkkonenMemory memory = new SimpleUkkonenMemory(totalBytes);
			ArrayList<byte[]> labelList = new ArrayList<byte[]>(200000000);
			labelFactory = new LabelRefBytesIndexFactory(labelList);
			treeHandler = new SimpleUkkonenSuffixTreeHandlerMemory(memory, labelFactory);

			SimpleUkkonenSuffixRootMemory root = new SimpleUkkonenSuffixRootMemory(memory.allocMemoryInternalNode(), treeHandler);

			UkkonenSuffixTree<LabelRefBytesIndex, UkkonenInternalSuffixNodeMemory, UkkonenLeafSuffixNodeMemory, UkkonenSuffixNodeMemory> tree = new UkkonenSuffixTree<LabelRefBytesIndex, UkkonenInternalSuffixNodeMemory, UkkonenLeafSuffixNodeMemory, UkkonenSuffixNodeMemory>(
					k, root);

			validReads = new BufferedReader(new FileReader(validReadsFileName));

			int count = 0;

			long lastCursor = 0;
			long lastLeafs = 0;
			long lastInternals = 0;
			long lastTime = System.currentTimeMillis();

			for (String validFileRead = validReads.readLine(); validFileRead != null; validFileRead = validReads.readLine()) {
				validFileRead = validFileRead.trim();
				if (validFileRead.length() > 0) {
					FastQ fastQ = new FastQ(validFileRead, k);
//				tree = Tools.buildSuffixTree(fastQ, tree);
					String dnaSeq;

					System.out.println("Starting:" + fastQ.fileFastQName);

					while ((dnaSeq = fastQ.getNextRead()) != null) {
						count++;
						char[] seqInverted = Tools.getCharsInverted(dnaSeq);
						byte[] seqBytesInverted = Tools.transformToBytes(seqInverted);
						labelList.add(seqBytesInverted);
						tree.addSuffixes(labelFactory.createLabel(labelList.size() - 1, 0, seqBytesInverted[0]));

						labelFactory.freeObjects();
						treeHandler.freeObjects();

						if (count % 1000000 == 0) {
							long currentTime = System.currentTimeMillis();
							long currentCursor = memory.getCursor();
							long currentLeafs = memory.leafsQtty;
							long currentInternals = memory.internalQtty;
							System.out.println(count + " , Time: " + (currentTime - timeInic) + " (" + (currentTime - lastTime) + ") Memory: " + currentCursor
									+ " (" + (currentCursor - lastCursor) + ") Leafs: " + (currentLeafs) + " (" + (currentLeafs - lastLeafs) + ") Internals: "
									+ (currentInternals) + " (" + (currentInternals - lastInternals) + ")");
							lastTime = currentTime;
							lastCursor = currentCursor;
							lastLeafs = currentLeafs;
							lastInternals = currentInternals;
						}

					}

					System.out.println(count);
					System.out.println("Finished:" + fastQ.fileFastQName);
					System.out.println();
				}
			}

//			store(root, validReadsFileName + ".suffixTree");

			matePairsHandler(matePairssFileName, root);

			System.out.println("Max Memory after build the tree " + Runtime.getRuntime().maxMemory());
			System.out.println("Total Memory after build the tree " + Runtime.getRuntime().totalMemory());
			System.out.println("Free Memory after build the tree " + Runtime.getRuntime().freeMemory());
			System.out.println("Time to build the tree : " + (System.currentTimeMillis() - timeInic));

			System.out.println("r1case1:" + r1case1);
			System.out.println("r1case1a:" + r1case1a);
			System.out.println("r1case2:" + r1case2);
			System.out.println("r1case2a:" + r1case2a);
			System.out.println("r1case3:" + r1case3);
			System.out.println();

//			BufferedWriter bw;
//			bw = new BufferedWriter(new FileWriter("tree" + System.currentTimeMillis(), false));
////			byte[] prefix = new byte[1];
////			prefix[0] = 0;
//			root.printWords(bw, "");
//			bw.flush();
//			System.out.println("Time to save the file: " + (System.currentTimeMillis() - time));

			validReads.close();

		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
		}
	}

	private static void store(SimpleUkkonenSuffixRootMemory root, String fileName) throws IOException {
		OutputStream out = null;
		try {
			byte[][] bytes = ((MemoryBytes) root.getTreeHandler().getMemory()).nodes;

			for (int i = 0; i < bytes.length; i++) {
				out = openOutputStream(new File(fileName + "." + i), false);
				out.write(bytes[i]);
				out.close();
			}
		} finally {
			try {
				if (out != null) {
					out.close();
				}
			} catch (IOException ioe) {
				// ignore
			}
		}
	}

	public static FileOutputStream openOutputStream(File file, boolean append) throws IOException {
		if (file.exists()) {
			if (file.isDirectory()) {
				throw new IOException("File '" + file + "' exists but is a directory");
			}
			if (file.canWrite() == false) {
				throw new IOException("File '" + file + "' cannot be written to");
			}
		} else {
			File parent = file.getParentFile();
			if (parent != null) {
				if (!parent.mkdirs() && !parent.isDirectory()) {
					throw new IOException("Directory '" + parent + "' could not be created");
				}
			}
		}
		return new FileOutputStream(file, append);
	}

	public static void matePairsHandler(String fileName, InternalNode<? extends LabelRefBytesIndex, ?, ?, ?> root) throws IOException {
		BufferedReader matePairsReads = new BufferedReader(new FileReader(fileName));

		String line;

		String file1, file2;
		String[] files;
		String line1File1;
		String line2File1;
		String line3File1;
		String line4File1;
		String line1File2;
		String line2File2;
		String line3File2;
		String line4File2;

		MatchReadCollection matches1, matches1a, matches2, matches2a;
		Read read1, read2;
		byte[] bytesRead1, bytesRead1a, bytesRead2, bytesRead2a;

		boolean gaps1, gaps1a, gaps2, gaps2a;
		int junctions1, junctions1a, junctions2, junctions2a;

		r1case1 = 0;
		r1case1a = 0;
		r1case2 = 0;
		r1case2a = 0;
		r1case3 = 0;

		while ((line = matePairsReads.readLine()) != null) {
			files = line.split(";");
			file1 = files[0];
			file2 = files[1];
			System.out.println("Starting the mate pair files:" + line);

			BufferedReader matePairsFile1 = new BufferedReader(new FileReader(file1));
			BufferedReader matePairsFile2 = new BufferedReader(new FileReader(file2));
			BufferedWriter matePairsFile1Result = new BufferedWriter(new FileWriter(file1 + ".fioma", false));
			BufferedWriter matePairsFile2Result = new BufferedWriter(new FileWriter(file2 + ".fioma", false));
//			BufferedWriter matePairsFile1ResultValidRead = new BufferedWriter(new FileWriter(file1 + ".fioma.validRead", false));
//			BufferedWriter matePairsFile2ResultValidRead = new BufferedWriter(new FileWriter(file2 + ".fioma.validRead", false));
			BufferedWriter matePairsFileLog = new BufferedWriter(new FileWriter(file1 + ".log", false));
			matePairsFileLog.write("read1\t");
			matePairsFileLog.write("read2\t");
			matePairsFileLog.write("matches1 Qtty\t");
			matePairsFileLog.write("matches1a Qtty\t");
			matePairsFileLog.write("matches2 Qtty\t");
			matePairsFileLog.write("matches2a Qtty\t");
			matePairsFileLog.write("gaps1 (true/false)\t");
			matePairsFileLog.write("gaps1a (true/false)\t");
			matePairsFileLog.write("gaps2 (true/false)\t");
			matePairsFileLog.write("gaps2a (true/false)\t");
			matePairsFileLog.write("junctions1 Qtty\t");
			matePairsFileLog.write("junctions1a Qtty\t");
			matePairsFileLog.write("junctions2 Qtty\t");
			matePairsFileLog.write("junctions2a Qtty\t");
			matePairsFileLog.write("matches1 [start size]\t");
			matePairsFileLog.write("matches1a [start size]\t");
			matePairsFileLog.write("matches2 [start size]\t");
			matePairsFileLog.write("matches2a [start size]");
			matePairsFileLog.newLine();

			while ((line1File1 = matePairsFile1.readLine()) != null) {
				line2File1 = matePairsFile1.readLine();
				line3File1 = matePairsFile1.readLine();
				line4File1 = matePairsFile1.readLine();

				line1File2 = matePairsFile2.readLine();
				line2File2 = matePairsFile2.readLine();
				line3File2 = matePairsFile2.readLine();
				line4File2 = matePairsFile2.readLine();

				read1 = new ReadStrings(line1File1, line2File1, line4File1);
				read2 = new ReadStrings(line1File2, line2File2, line4File2);
//				InternalNode<? extends LabelRefBytesIndex, ?, ?, ?> node = root;

				// try to find out the inverted sequence
				bytesRead1 = read1.getSequenceBytesInverted();
				bytesRead1a = read1.getSequenceBytesComplementar();
				bytesRead2 = read2.getSequenceBytesInverted();
				bytesRead2a = read2.getSequenceBytesComplementar();

				matches1 = getMatches(bytesRead1, root);
				matches1a = getMatches(bytesRead1a, root);
				matches2 = getMatches(bytesRead2, root);
				matches2a = getMatches(bytesRead2a, root);

				gaps1 = hasGaps(matches1, e, read1.getLength() - s);
				gaps1a = hasGaps(matches1a, s, read1.getLength() - e);
				gaps2 = hasGaps(matches2, e, read2.getLength() - s);
				gaps2a = hasGaps(matches2a, s, read2.getLength() - e);

				junctions1 = matches1.getJunctionIndexes().size();
				junctions1a = matches1a.getJunctionIndexes().size();
				junctions2 = matches2.getJunctionIndexes().size();
				junctions2a = matches2a.getJunctionIndexes().size();

				printMatePairResult(read1, matches1, matches1a, gaps1, gaps1a, junctions1, junctions1a, matePairsFile1Result);
				printMatePairResult(read2, matches2, matches2a, gaps2, gaps2a, junctions2, junctions2a, matePairsFile2Result);
				// flag is 1 if mismatch is in the end of the valid read otherwise is zero (0)
				printLog(read1, matches1, matches1a, gaps1, gaps1a, junctions1, junctions1a, read2, matches2, matches2a, gaps2, gaps2a, junctions2,
						junctions2a, matePairsFileLog);

				// free objects to be used in the next read
				matchCollectionFactory.freeMatchCollection(matches1);
				matchCollectionFactory.freeMatchCollection(matches1a);
				matchCollectionFactory.freeMatchCollection(matches2);
				matchCollectionFactory.freeMatchCollection(matches2a);
				Match.freePool();
				labelFactory.freeObjects();
				treeHandler.freeObjects();
			}
			matePairsFile1.close();
			matePairsFile2.close();
			matePairsFile1Result.flush();
			matePairsFile1Result.close();
			matePairsFile2Result.flush();
			matePairsFile2Result.close();
			matePairsFileLog.flush();
			matePairsFileLog.close();
		}
		matePairsReads.close();
	}

	private static void printLog(Read read1, MatchReadCollection matches1, MatchReadCollection matches1a, boolean gaps1, boolean gaps1a, int junctions1,
			int junctions1a, Read read2, MatchReadCollection matches2, MatchReadCollection matches2a, boolean gaps2, boolean gaps2a, int junctions2,
			int junctions2a, BufferedWriter matePairsFileLog) throws IOException {
//		matePairsFileLog.write("read1\t");
//		matePairsFileLog.write("read2\t");
//		matePairsFileLog.write("matches1 Qtty\t");
//		matePairsFileLog.write("matches1a Qtty\t");
//		matePairsFileLog.write("matches2 Qtty\t");
//		matePairsFileLog.write("matches2a Qtty\t");
//		matePairsFileLog.write("gaps1 (true/false)\t");
//		matePairsFileLog.write("gaps1a (true/false)\t");
//		matePairsFileLog.write("gaps2 (true/false)\t");
//		matePairsFileLog.write("gaps2a (true/false)\t");
//		matePairsFileLog.write("junctions1 Qtty\t");
//		matePairsFileLog.write("junctions1a Qtty\t");
//		matePairsFileLog.write("junctions2 Qtty\t");
//		matePairsFileLog.write("junctions2a Qtty\t");
//		matePairsFileLog.write("matches1 [start size]\t");
//		matePairsFileLog.write("matches1a [start size]\t");
//		matePairsFileLog.write("matches2 [start size]\t");
//		matePairsFileLog.write("matches2a [start size]");

		matePairsFileLog.write(read1.getId());
		matePairsFileLog.write('\t');
		matePairsFileLog.write(read2.getId());
		matePairsFileLog.write('\t');
		matePairsFileLog.write(matches1.size() + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(matches1a.size() + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(matches2.size() + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(matches2a.size() + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(gaps1 ? "True" : "False");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(gaps1a ? "True" : "False");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(gaps2 ? "True" : "False");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(gaps2a ? "True" : "False");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(junctions1 + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(junctions1a + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(junctions2 + "");
		matePairsFileLog.write('\t');
		matePairsFileLog.write(junctions2a + "");
		matePairsFileLog.write('\t');
		Match match;
		for (int i = 0; i < matches1.size(); i++) {
			match = matches1.getMatch(i);
			matePairsFileLog.write('(');
			matePairsFileLog.write((read1.getLength() - match.getMismatchPositionWord()) + "");
			matePairsFileLog.write(' ');
			matePairsFileLog.write(match.getLength() + "");
			matePairsFileLog.write(')');
		}
		matePairsFileLog.write('\t');
		for (int i = 0; i < matches1a.size(); i++) {
			match = matches1a.getMatch(i);
			matePairsFileLog.write('(');
			matePairsFileLog.write(match.getStartPositionWord() + "");
			matePairsFileLog.write(' ');
			matePairsFileLog.write(match.getLength() + "");
			matePairsFileLog.write(')');
		}
		matePairsFileLog.write('\t');
		for (int i = 0; i < matches2.size(); i++) {
			match = matches2.getMatch(i);
			matePairsFileLog.write('(');
			matePairsFileLog.write((read2.getLength() - match.getMismatchPositionWord()) + "");
			matePairsFileLog.write(' ');
			matePairsFileLog.write(match.getLength() + "");
			matePairsFileLog.write(')');
		}
		matePairsFileLog.write('\t');
		for (int i = 0; i < matches2a.size(); i++) {
			match = matches2a.getMatch(i);
			matePairsFileLog.write('(');
			matePairsFileLog.write(match.getStartPositionWord() + "");
			matePairsFileLog.write(' ');
			matePairsFileLog.write(match.getLength() + "");
			matePairsFileLog.write(')');
		}
		matePairsFileLog.newLine();
	}

	private static void printMatePairResult(Read read, MatchReadCollection matches, MatchReadCollection matchesa, boolean gaps, boolean gapsa, int junctions,
			int junctionsa, BufferedWriter matePairsFileResult) throws IOException {
		int junction;
		if (!gaps && junctions == 0) {
			printMatePair(read, read.getLength() - matches.getMismatchPositionLastMatch(), read.getLength() - matches.getInitialPositionFirstMatch(),
					matePairsFileResult);
			r1case1++;
		} else if (!gapsa && junctionsa == 0) {
			printMatePair(read, matchesa.getInitialPositionFirstMatch(), matchesa.getMismatchPositionLastMatch(), matePairsFileResult);
			r1case1a++;
		} else if (!gaps && junctions == 1) {
			junction = matches.getMatch(matches.getJunctionIndexes().get(0) - 1).getMismatchPositionWord();
			printMatePair(read, read.getLength() - matches.getMismatchPositionLastMatch(), read.getLength() - junction, matePairsFileResult);
			r1case2++;
		} else if (!gapsa && junctionsa == 1) {
			junction = matchesa.getMatch(matchesa.getJunctionIndexes().get(0)).getStartPositionWord();
			printMatePair(read, matchesa.getInitialPositionFirstMatch(), junction, matePairsFileResult);
			r1case2a++;
		} else {
			// the mate pair doesn't have a good alignment
			printMatePair(read, 0, read.getLength(), matePairsFileResult);
			r1case3++;
		}
	}

	private static void printMatePair(Read read1, int start, int end, BufferedWriter matePairsFileResult) throws IOException {
		matePairsFileResult.write(read1.getId());
		matePairsFileResult.newLine();
		matePairsFileResult.write(read1.getSequence().substring(start, end));
		matePairsFileResult.newLine();
		matePairsFileResult.write('+');
		matePairsFileResult.newLine();
		matePairsFileResult.write(read1.getQuality());
		matePairsFileResult.newLine();
	}

	public static MatchReadCollection getMatches(byte[] bytesRead, InternalNode<? extends LabelRefBytesIndex, ?, ?, ?> root) {
		MatchReadCollection ret = matchCollectionFactory.getMatchCollection();

//		byte[] bytesRead = read.getSequenceBytesInverted();
		int wordSize = bytesRead[0];

		int startPositionWord = 0;
		Match match = find(root, 0, bytesRead, startPositionWord, m);
		match.setStartPositionWord(startPositionWord);
		ret.addMatchSorted(match);

		while (match.getMismatchPositionWord() < wordSize - e) {
			if (match.getMismatchPositionWord() - k > startPositionWord) {
				startPositionWord = match.getMismatchPositionWord() - k;
			}
			startPositionWord++;
			match = find(root, 0, bytesRead, startPositionWord, m);
			match.setStartPositionWord(startPositionWord);
			ret.addMatchSorted(match);
		}
		return ret;
	}

	public static boolean hasGaps(MatchReadCollection matches, int minimumStart, int minimumLastMismatch) {
		return matches.getGapIndexes().size() > 0 || matches.getMismatchPositionLastMatch() < minimumLastMismatch
				|| matches.getInitialPositionFirstMatch() >= minimumStart;
	}

	// analyze will be started at posLabel position and posWord position
	public static Match find(Node<? extends LabelRefBytesIndex, ?, ?, ?> node, int posLabel, byte[] word, int posWord, int mismatches) {
		LabelRefBytesIndex label = node.getLabel();
		int labelLength;
		int lettersMatched;
		// test if is root
		if (label == null) {
			labelLength = 0;
			lettersMatched = 0;
		} else {
			labelLength = label.getLength();
			lettersMatched = Tools
					.getMismatch(label.getWord().getWord(), label.getStart() + posLabel, labelLength - posLabel, word, posWord, word[0] - posWord);
			if (lettersMatched == -1) {
				lettersMatched = labelLength - posLabel;
			}
			posLabel += lettersMatched;
			posWord += lettersMatched;
		}
		if (posWord >= word[0]) {
			// whole word was found. The word is finished.
			return Match.getInstance(node, posLabel, posWord, posWord);
		} else if (posLabel >= labelLength) {
			// The label is finished. Search the next node.
			if (node.isLeaf()) {
				// the word reached a leaf, impossible to continue. The tree is finished.
				return Match.getInstance(node, posLabel, posWord, posWord);
			} else {
				byte firstLetter = Tools.getByte(word, posWord);
				Node<? extends LabelRefBytesIndex, ?, ?, ?> nextNode = ((InternalNode<? extends LabelRefBytesIndex, ?, ?, ?>) node).nextNode(firstLetter);
				if (nextNode == null) {
					if (mismatches > 0) {
						posLabel = 1;
						posWord++;
						mismatches--;
						Node<? extends LabelRefBytesIndex, ?, ?, ?>[] nodes = ((InternalNode<? extends LabelRefBytesIndex, ?, ?, ?>) node).getChilds();
						int bestLength = -1;
						Match bestMatch = null;
						Match matchAux;
						for (int i = 0; i < nodes.length; i++) {
							if (nodes[i] != null) {
								matchAux = find(nodes[i], posLabel, word, posWord, mismatches);
								if (matchAux.getLength() > bestLength) {
									bestMatch = matchAux;
									bestLength = matchAux.getLength();
								}
							}
						}
						return bestMatch;
					} else {
						return Match.getInstance(node, posLabel, posWord, posWord);
					}
				} else {
					return find(nextNode, 1, word, ++posWord, mismatches);
				}
			}
		} else {
			// has found a mismatch inside the label
			if (mismatches > 0) {
				posLabel++;
				posWord++;
				mismatches--;
				return find(node, posLabel, word, posWord, mismatches);
			} else {
				return Match.getInstance(node, posLabel, posWord, posWord);
			}
		}
	}
}
